package com.likou;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class q148 {

//    public ListNode sortList(ListNode head) {
//        if (head == null || head.next == null) {
//            return head;
//        }
//        ListNode p = head;
//        List<Integer> list = new ArrayList<>();
//
//        while (p != null) {
//            list.add(p.val);
//            p = p.next;
//        }
//
//        // 归并排序
//        MergeSort(list, 0, list.size() - 1);
//
//        p = head;
//        int mark = 0;
//        while (p != null) {
//            p.val = list.get(mark);
//            mark++;
//            p = p.next;
//        }
//
//        return head;
//    }
//
//    private void MergeSort(List<Integer> list, int left, int right) {
//        if (left >= right) {
//            return;
//        }
//        int mid = (left + right) / 2;
//        MergeSort(list, left, mid);
//        MergeSort(list, mid + 1, right);
//
//        List<Integer> temp = new ArrayList<>();
//        int p = left;
//        int q = mid + 1;
//        while (p <= mid && q <= right) {
//            if (list.get(p) < list.get(q)) {
//                temp.add(list.get(p));
//                p++;
//            } else {
//                temp.add(list.get(q));
//                q++;
//            }
//        }
//
//        while (p <= mid) {
//            temp.add(list.get(p));
//            p++;
//        }
//        while (q <= right) {
//            temp.add(list.get(q));
//            q++;
//        }
//
//        for (int i = left, j = 0; i <= right; i++, j++) {
//            list.set(i, temp.get(j));
//        }
//    }


//    public ListNode sortList(ListNode head) {
//        int[] a = new int[5 * 10000];
//        ListNode p = head;
//        int i = 0;
//        // 拷贝到数组
//        while (p != null) {
//            a[i++] = p.val;
//            p = p.next;
//        }
//        // 排序
//        Arrays.sort(a, 0, i);
//        p = head;
//        i = 0;
//        // 拷贝到链表
//        while (p != null) {
//            p.val = a[i++];
//            p = p.next;
//        }
//        return head;
//    }


    // 快排
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode p = head;
        List<Integer> list = new ArrayList<>();

        while (p != null) {
            list.add(p.val);
            p = p.next;
        }

        // 快排算法 时间复杂度O(NlogN)
        quickSort1(list, 0, list.size() - 1);

        p = head;
        int mark = 0;
        while (p != null) {
            p.val = list.get(mark);
            mark++;
            p = p.next;
        }

        return head;
    }

//    private int partition(List<Integer> list, int left, int right) {
//        // 基准元素
//        Integer pivot = list.get(right);
//        // 位置
//        int index = left;
//
//        for (int i = left; i < right; i++) {
//            if (list.get(i) < pivot) {
//                Integer temp = list.get(i);
//                list.set(i, list.get(index));
//                list.set(index, temp);
//                index++;
//            }
//        }
//
//        list.set(right, list.get(index));
//        list.set(index, pivot);
//
//        return index;
//    }
//
//    private void quickSort(List<Integer> list, int left, int right) {
//        if (left < right) {
//            int partition = partition(list, left, right);
//            quickSort(list, left, partition - 1);
//            quickSort(list, partition + 1, right);
//        }
//
//    }

    private void quickSort1(List<Integer> list, int left, int right) {
        if (left >= right) {
            return;
        }
        // 基准元素
        Integer pivot = list.get(right);
        // 位置
        int index = left;

        for (int i = left; i < right; i++) {
            if (list.get(i) < pivot) {
                Integer temp = list.get(i);
                list.set(i, list.get(index));
                list.set(index, temp);
                index++;
            }
        }

        list.set(right, list.get(index));
        list.set(index, pivot);

        quickSort1(list, left, index - 1);
        quickSort1(list, index + 1, right);

    }


    // 超时
//    public ListNode sortList(ListNode head) {
//        if (head == null || head.next == null) {
//            return head;
//        }
//        ListNode p = head;
//        ListNode q = head.next;
//        while (p != null && q != null) {
//            if (q.val < p.val) {
//                int temp = p.val;
//                p.val = q.val;
//                q.val = temp;
//            }
//            if (q.next == null) {
//                p = p.next;
//                q = p.next;
//            } else {
//                q = q.next;
//            }
//        }
//        return head;
//    }
}
